﻿#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;
typedef unsigned long long ULONG64;
typedef long long LONG64;

typedef struct  
{
	int x;
	int height;
	bool add;
	char padding[3];
} TheSkylineData;

#define N 3

static bool sortSkylineData(const TheSkylineData& dat1, const TheSkylineData& dat2)
{
	if (dat1.x == dat2.x)
	{
		return dat1.add > dat2.add;
	}

	return dat1.x < dat2.x;
}

static ULONG64* resultAddr = nullptr;

static LONG64** outlineMatrix(const int* matrix, const size_t lineCount, size_t* resultLineCount)
{
	map<int, int> xToMaxHeightMap;
	map<int, int> heightToFrequencyMap;
	vector<TheSkylineData> lineDataVec;

	int start;
	int end;
	int height;
	TheSkylineData curData;

	for (int line = 0; line < lineCount; line++)
	{
		start = matrix[0 + line * N];
		end = matrix[1 + line * N];
		height = matrix[2 + line * N];
		curData.x = start;
		curData.height = height;
		curData.add = true;
		lineDataVec.push_back(curData);
		curData.x = end;
		curData.height = height;
		curData.add = false;
		lineDataVec.push_back(curData);
	}

	sort(lineDataVec.begin(), lineDataVec.end(), sortSkylineData);
	
	int x;
	bool add;
	int freq;
	int curMaxHeight;
	map<int, int>::reverse_iterator heightToFrequencyIterator;
	for (auto it = lineDataVec.begin(); it != lineDataVec.end(); it++)
	{
		x = it->x;
		height = it->height;
		add = it->add;
		if (add)
		{
			if (!heightToFrequencyMap.count(height))
			{
				heightToFrequencyMap[height] = 1;
			}
			else
			{
				heightToFrequencyMap[height]++;
			}
		}
		else
		{
			if (heightToFrequencyMap.count(height))
			{
				freq = heightToFrequencyMap[height];
				--freq;
				if (freq <= 0)
				{
					heightToFrequencyMap.erase(height);
				}
				else
				{
					heightToFrequencyMap[height] = freq;
				}
			}
		}

		heightToFrequencyIterator = heightToFrequencyMap.rbegin();
		if (heightToFrequencyIterator != heightToFrequencyMap.rend())
		{
			xToMaxHeightMap[x] = heightToFrequencyIterator->first;
		}
		else
		{
			xToMaxHeightMap[x] = 0;
		}
	}

	int prevHeight = 0;
	int curHeight;
	int index = 0;
	int count = xToMaxHeightMap.size();
	int prevX;
	vector<int> result;

	for (auto it = xToMaxHeightMap.begin(); it != xToMaxHeightMap.end(); it++)
	{
		x = it->first;
		curHeight = it->second;
		if (curHeight == prevHeight)
		{
			++index;
			continue;
		}

		if (index > 0 && prevHeight > 0)
		{
			result.push_back(prevX);
			result.push_back(x);
			result.push_back(prevHeight);
		}

		prevHeight = curHeight;
		prevX = x;
		++index;
	}

	xToMaxHeightMap.clear();
	heightToFrequencyMap.clear();

	LONG64* resultMatrix;
	resultMatrix = (LONG64*)malloc(result.size() * sizeof(LONG64));
	memset(resultMatrix, 0, result.size() * sizeof(LONG64));
	for (int i = 0; i < result.size(); i++)
	{
		resultMatrix[i] = result[i];
	}

	*resultLineCount = result.size() / N;
	resultAddr = (ULONG64*)malloc(sizeof(ULONG64) * (*resultLineCount));
	memset(resultAddr, 0, sizeof(ULONG64)* (*resultLineCount));
	LONG64** pResultMatrix;
	pResultMatrix = (LONG64**)resultAddr;

	for (int i = 0; i < *resultLineCount; i++)
	{
		pResultMatrix[i] = (LONG64*)(&resultMatrix[i * N]);
	}
	
	return pResultMatrix;
}

/**
 * 给定一个Nx3的矩阵matrix，对于每一个长度为3的小数组arr，都表示一个大楼的三个数据。arr[0]表示大楼的左边界，arr[1]表示大楼的右边界，arr[2]表示大楼的高度(一定＞0). 每座大楼的地基都在X轴上，大楼之间可能会有重叠，请返回整体的轮廓线数组。
 * 
 * 举例:
 * matrix = {
     {2,5,6},
	 {1,7,4},
	 {4,6,7},
	 {3,6,5},
	 {10,13,2},
	 {9,11,3},
	 {12,14,4},
	 {10,12,5},
   }

   返回: {
     {1,2,4},
	 {2,4,6},
	 {4,6,7},
	 {6,7,4},
	 {9,10,3},
	 {10,12,5},
	 {12,14,4},
   }

   思路：
   根据高度的变化，定制一个结构：
   struct Data {
     int x;
	 int height;
	 bool add; // 是否增加高度
   }

   根据每个矩形的边缘，定义好数据，并优先根据x排序，x相同，则add==true排前面。
   根据例子，有dataArr:
   [{1,4,true},{2,6,true},{3,5,true},{4,7,true},{5,6,false},{6,5,false},{6,7,false},{7,4,false},{9,3,true},{10,5,true},{10,2,true},{11,3,false},{12,4,true},{12,5,false},{13,2,false},{14,4,false}]

   再声明2个map，一个是x坐标->该坐标的最大楼高 xToMaxHeightMap；一个是高度->该高度出现的频次 heightToCountMap。
   按照顺序依次处理dataArr中的数据，去填写2个map。
   比如：
   {1,4,true},   xToMaxHeightMap[1]=4, heightToCountMap[4]=1
   {2,6,true},   xToMaxHeightMap[2]=6, heightToCountMap[6]=1
   {3,5,true},   xToMaxHeightMap[3]=6, heightToCountMap[5]=1
   {4,7,true},   xToMaxHeightMap[4]=7, heightToCountMap[7]=1
   {5,6,false},  xToMaxHeightMap[5]=7, heightToCountMap[6]=0, 去掉heightToCountMap[6]
   ...

   每过一个data, 当data.add==true时，把当前data的楼高记入heightToCountMap，之前无此高度，则设为1，有此高度则+1；当data.add==false时，heightToCountMap中对应data.height高度的key -1，如果减为0则去掉这个key，然后当前x坐标的最大高度从heightToCountMap中取key最大的key更新xToMaxHeightMap结构，即xToMaxHeightMap[data.x]=maxKey.

   最后，根据xToMaxHeightMap中的数据，整理出最终要输出的结果.

 */
int main_theSkylineProblem()
{
	int matrix[][N] = {
	 {2,5,6},
	 {1,7,4},
	 {4,6,7},
	 {3,6,5},
	 {10,13,2},
	 {9,11,3},
	 {12,14,4},
	 {10,12,5},
	};

	size_t lineCount = sizeof(matrix) / (sizeof(int) * N);
	size_t resultLineCount = 0;
	auto result = outlineMatrix(matrix[0], lineCount, &resultLineCount);

	for (int i = 0; i < resultLineCount; i++)
	{
		printf("(%d,%d,%d)\n", result[i][0], result[i][1], result[i][2]);
	}

	free(result[0]);
	free(resultAddr);

	return 0;
}